//
// Created by 张朝辉 on 2023/9/19.
//
/*
#include "fa/dfa.h"
#include "fa/nfa.h"
#include "pda/dpda.h"
#include "pda/npda.h"
#include "tm/rulebook.h"
#include "tm/mvd.h"
#include "tm/tape.h"
#include "tm/dtm.h"
#include <iostream>

using namespace std;
int main(){
    // 定义DFA，判断是否一个串中是否存在01
    map<pair<string ,char>,string> rule_table;
    rule_table[make_pair("a",'0')] = "b";
    rule_table[make_pair("a",'1')] = "a";
    rule_table[make_pair("b",'0')] = "b";
    rule_table[make_pair("b",'1')] = "c";
    rule_table[make_pair("c",'0')] = "c";
    rule_table[make_pair("c",'1')] = "c";

    auto *d = new DFA({"a","b","c"},{'1','0'},"a",{"c"},rule_table);
    try {
        if(d->isAccept_str("010")){
            cout<<"成功匹配到含有01的串"<<endl;
        }else{
            cout<<"测试的串中不含01"<<endl;
        }
    }catch (char const* s){
        cout << s <<endl;
    }

    delete d;

//  --------------------------------------------------------------------------------------------------------------------
    // 将DFA转换为正则表达式
    map<pair<string ,char>,string> rule_table0;
    rule_table0[make_pair("a",'0')] = "b";
    rule_table0[make_pair("a",'1')] = "a";

    rule_table0[make_pair("b",'0')] = "b";
    rule_table0[make_pair("b",'1')] = "b";

    auto *dr = new DFA({"a","b"},{'1','0'},"a",{"b"},rule_table0);
    cout<<dr->DFA2Regex();
    // ((0+(1+ε).(1+ε)*.0)+(0+(1+ε).(1+ε)*.0).((0+1+ε)+Φ.(1+ε)*.0)*.((0+1+ε)+Φ.(1+ε)*.0))
    delete dr;

//  -------------------------------------------------------------------------------------------------------------------------------

    // 定义DFA，判断一个01串中是否存在偶数个0和偶数个1
    map<pair<string,char>,string> rule_table2;
    rule_table2[make_pair("a",'0')] = "c";
    rule_table2[make_pair("a",'1')] = "b";
    rule_table2[make_pair("b",'0')] = "d";
    rule_table2[make_pair("b",'1')] = "a";
    rule_table2[make_pair("c",'0')] = "a";
    rule_table2[make_pair("c",'1')] = "d";
    rule_table2[make_pair("d",'0')] = "b";
    rule_table2[make_pair("d",'1')] = "c";

    auto *d2 = new DFA({"a","b","c","d"},{'1','0'},"a",{"a"},rule_table2);
    try{
        if(d2->isAccept_str("01011")){
            cout << "存在偶数个01" << endl;
        } else{
            cout << "不存在偶数个01" << endl;
        }
    }catch(char const* s){
        cout << s <<endl;
    }

    delete d2;
//  --------------------------------------------------------------------------------------------------------------------------------------------
    // 定义DFA，判断一个字符串是否以00结尾
    map<pair<string,char>,string> rule_table3;
    rule_table3[make_pair("a",'1')] = "a";
    rule_table3[make_pair("a",'0')] = "b";
    rule_table3[make_pair("b",'0')] = "c";
    rule_table3[make_pair("b",'1')] = "a";
    rule_table3[make_pair("c",'0')] = "c";
    rule_table3[make_pair("c",'1')] = "a";

    auto *d3 = new DFA({"a","b","c"},{'1','0'},"a",{"c"},rule_table3);
    try{
        if(d3->isAccept_str("001001")){
            cout<<"该字符串是以00结尾"<<endl;
        } else{
            cout<<"该字符串并不是以00结尾"<<endl;
        }
    }catch (char const* s){
        cout << s << endl;
    }

    delete d3;
//  -------------------------------------------------------------------------------------------------------------------------------------------
    // 定义NFA，匹配以01结尾的串
    cout << "定义NFA识别以01结尾的串:\t";
    map<pair<string,char>,set<string>> rule_table4;
    rule_table4[make_pair("a",'0')] = {"a","b"};
    rule_table4[make_pair("a",'1')] = {"a"};
    rule_table4[make_pair("b",'1')] = {"c"};
    auto *nfa = new NFA({"a","b","c"},{'0','1'},"a",{"c"},rule_table4);
    if(nfa->isAccept_str("0101010101")){
        cout<<"成功识别到以01结尾的串";
    } else{
        cout<<"识别失败";
    }
    cout<<"\t将NFA转换为dfa进行测试:\t";
    auto dz = nfa->NFA2DFA();
    if(dz.isAccept_str("0101010101")){
        cout<<"成功识别到以01结尾的串"<<endl;
    }else{
        cout<<"识别失败"<<endl;
    }
    delete nfa;
//  --------------------------------------------------------------------------------------
    // 定义NFA，匹配以01开始或者以01结尾的字符串
    cout <<"定义NFA，识别以01开始或者以01结尾的字符串:\t";
    map<pair<string,char>,set<string>> rule_table5;
    rule_table5[make_pair("a",'0')] = {"b","d"};
    rule_table5[make_pair("a",'1')] = {"d"};
    rule_table5[make_pair("b",'1')] = {"c"};
    rule_table5[make_pair("c",'0')] = {"c"};
    rule_table5[make_pair("c",'1')] = {"c"};
    rule_table5[make_pair("d",'0')] = {"d","e"};
    rule_table5[make_pair("d",'1')] = {"d"};
    rule_table5[make_pair("e",'1')] = {"f"};
    auto *nfa2 = new NFA({"a","b","c","d","e","f"},{'0','1'},"a",{"c","f"},rule_table5);
    if(nfa2->isAccept_str("0101011110")){
        cout << "识别成功，该字符串以01开始或结尾\t";
    }else{
        cout << "识别失败\t";
    }
    cout<<"将NFA转换为dfa进行测试:\t";
    auto dz2 = nfa2->NFA2DFA();
    if(dz2.isAccept_str("0101011110")){
        cout<<"识别成功，该字符串以01开始或结尾"<<endl;
    }else{
        cout<<"识别失败"<<endl;
    }
    delete nfa2;
//  --------------------------------------------------------------------------------------------------------------
    // 定义eNFA，匹配倒数三个字符至少有一个是1的串,ε使用'\0'替代
    cout<<"定义eNFA，识别倒数三个字符至少有一个是1的串:\t";
    map<pair<string,char>,set<string>> rule_table6;
    rule_table6[make_pair("a",'0')] = {"a"};
    rule_table6[make_pair("a",'1')] = {"a","b"};

    rule_table6[make_pair("b",'0')] = {"c"};
    rule_table6[make_pair("b",'1')] = {"c"};
    rule_table6[make_pair("b",'\0')] = {"c"};

    rule_table6[make_pair("c",'0')] = {"d"};
    rule_table6[make_pair("c",'1')] = {"d"};
    rule_table6[make_pair("c",'\0')] = {"d"};

    auto *nfa3 = new NFA({"a","b","c","d"}, {'0','1'}, "a", {"d"}, rule_table6);
    if(nfa3->isAccept_str("000010001")){
        cout << "倒数三个字符中含有1\t";
    }else{
        cout << "识别失败\t";
    }

    cout<<"将NFA转换为DFA进行测试:\t";
    auto d4 = nfa3->NFA2DFA();
    if(d4.isAccept_str("000010001")){
        cout << "倒数三个字符中含有1" <<endl;
    }else{
        cout << "识别失败" <<endl;
    }
    delete nfa3;
//  --------------------------------------------------------------------------------------------

    // 将一个正则表达式转换为NFA并判断由此正则表达式所表示的串能否被自动机识别
    NFA n = NFA::Re2NFA("(0.0.(0+1.0)*)*.(a+b.c)*");
    if(n.isAccept_str("00001000100aaabcaabcbc")){
        cout << "由正则表达式转换成的自动机能正确识别此串" << endl;
    }else {
        cout << "无法识别此串" << endl;
    }
//  -------------------------------------------------------------------------------------------------------------------

    map<Tuple3,pair<string,string>> rule_table7;
    rule_table7[Tuple3{"a",'0','#'}] = make_pair("a","0#");
    rule_table7[Tuple3{"a",'1','#'}] = make_pair("a","1#");
    rule_table7[Tuple3{"a",'0','0'}] = make_pair("a","00");
    rule_table7[Tuple3{"a",'0','1'}] = make_pair("a","01");
    rule_table7[Tuple3{"a",'1','0'}] = make_pair("a","10");
    rule_table7[Tuple3{"a",'1','1'}] = make_pair("a","11");

    rule_table7[Tuple3{"a",'2','#'}] = make_pair("b","#");
    rule_table7[Tuple3{"a",'2','0'}] = make_pair("b","0");
    rule_table7[Tuple3{"a",'2','1'}] = make_pair("b","1");

    rule_table7[Tuple3{"b",'0','0'}] = make_pair("b","\0");
    rule_table7[Tuple3{"b",'1','1'}] = make_pair("b","\0");

    rule_table7[Tuple3{"b",'\0','#'}] = make_pair("c","#");
    auto *dpda = new DPDA({"a","b","c"},{'0','1','2'},{'0','1','#'},rule_table7,"a",'#',{"c"});
    if(dpda->isAccept_str("020")){
        cout<<"该字符串可以被此DPDA接受"<<endl;
    }else{
        cout<<"该字符串不能被此DPDA接受"<<endl;
    }
    delete dpda;
//  -------------------------------------------------------------------------------------------------------------------
    map<Tuple3,set<pair<string,string>>> rule_table8;
    rule_table8[Tuple3{"a",'0','#'}] = {make_pair("a","0#")};
    rule_table8[Tuple3{"a",'1','#'}] = {make_pair("a","1#")};
    rule_table8[Tuple3{"a",'0','0'}] = {make_pair("a","00")};
    rule_table8[Tuple3{"a",'0','1'}] = {make_pair("a","01")};
    rule_table8[Tuple3{"a",'1','0'}] = {make_pair("a","10")};
    rule_table8[Tuple3{"a",'1','1'}] = {make_pair("a","11")};

    rule_table8[Tuple3{"a",'\0','#'}] = {make_pair("b","#")};
    rule_table8[Tuple3{"a",'\0','0'}] = {make_pair("b","0")};
    rule_table8[Tuple3{"a",'\0','1'}] = {make_pair("b","1")};

    rule_table8[Tuple3{"b",'0','0'}] = {make_pair("b","\0")};
    rule_table8[Tuple3{"b",'1','1'}] = {make_pair("b","\0")};

    rule_table8[Tuple3{"b",'\0','#'}] = {make_pair("c","#")};
    auto *npda = new NPDA({"a","b","c"},{'1','0'},{'1','0','#'},rule_table8,"a",'#',{"c"});
    if(npda->isAccept_str("101110011101")){
        cout << "该字符串可以被此NPDA接受";
    }else{
        cout << "该字符串无法被此NPDA接受";
    }
    delete npda;

    RuleBook ruleBook;
    ruleBook.addRule("1",'x','x',mvd::RIGHT,"1")
            ->addRule("1",'_','_',mvd::LEFT,"6")
            ->addRule("1",'a','x',mvd::RIGHT,"2")
            ->addRule("2",'a','a',mvd::RIGHT,"2")
            ->addRule("2",'x','x',mvd::RIGHT,"2")
            ->addRule("2",'b','x',mvd::RIGHT,"3")
            ->addRule("3",'b','b',mvd::RIGHT,"3")
            ->addRule("3",'x','x',mvd::RIGHT,"3")
            ->addRule("3",'c','x',mvd::RIGHT,"4")
            ->addRule("4",'c','c',mvd::RIGHT,"4")
            ->addRule("4",'_','_',mvd::LEFT,"5")
            ->addRule("5",'a','a',mvd::LEFT,"5")
            ->addRule("5",'b','b',mvd::LEFT,"5")
            ->addRule("5",'c','c',mvd::LEFT,"5")
            ->addRule("5",'x','x',mvd::LEFT,"5")
            ->addRule("5",'_','_',mvd::RIGHT,"1");

    ruleBook.setStartState("1");
    ruleBook.setFinalStateSet({"6"});
    Tape tape{"______aabbcc_",6};
    DTM dtm{ruleBook,tape};
    dtm.execute();

    return 0;
}

*/